package com.tgy.algorithm.base._动态规划;

import java.util.HashMap;

/**
 *
 * 给定一个字符串str，给定一个字符串类型的数组arr。
 * arr里的每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。
 * 返回需要至少多少张贴纸可以完成这个任务
 * 例子:
 * str= "babac",
 * arr = {"ba","c","abcd"}
 * 至少需要两张贴纸"ba"和"abcd"，因为使用这两张贴纸，把每一个字符单独剪开，含有2个a、2个b、1个c。
 * 是可以拼出str的。所以返回2。
 *
 * str - arr[i] ,往下走，
 */
public class _贴纸问题 {

    public static int getMinPage(String content,String[] pages) {

        int pageLen = pages.length;

        int[] contentTable = new int[26];

        char[] charArray = content.toCharArray();
        for (char c : charArray) {
            contentTable[c - 'a']++;
        }

        int[][] nums = new int[pageLen][26];

        for (int i = 0; i < pageLen; i++) {
            char[] chars = pages[i].toCharArray();
            for (char ch:chars) {
                nums[i][ch - 'a']++;
            }
        }
        HashMap<String, Integer> cache = new HashMap<>();
        return doGetMinPage(contentTable,nums,cache);
    }

    public static int doGetMinPage(int[] contentNums,int[][] pagesNums,HashMap<String, Integer> cache) {

        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < contentNums.length; i++) {
            int count = contentNums[i];
            if (count != 0) {
                for (int j = 0; j < count; j++) {
                    char c = (char) (i + 'a');
                    sb.append(c);
                }
            }
        }

        String contentStr = sb.toString();
        if (contentStr.isEmpty()) {
            return 0;
        }

        Integer cacheCount = cache.get(contentStr);

        if (cacheCount != null) {
            return cacheCount;
        }

        int retVal = Integer.MAX_VALUE;
        for (int i = 0; i < pagesNums.length; i++) {

            int[] cpContent = copyContentNums(contentNums);
            int[]  pageNum = pagesNums[i];

            boolean flag = false;
            for (int j = 0; j < cpContent.length; j++) {
                if(cpContent[j] == 0 || (pageNum[j] == 0)) {
                    continue;
                }
                int count = cpContent[j] - pageNum[j];
                if (count >= 0) {
                    cpContent[j] = count;
                    flag = true;
                }
            }
            if (!flag) {
                // 没有对cpContent进行减员，排除无线递归的情况
                continue;
            }
            int nextVal = doGetMinPage(cpContent,pagesNums,cache);
            if (nextVal >= 0) {
                retVal = Math.min(retVal, nextVal + 1);
            }
        }

        cache.put(contentStr,retVal == Integer.MAX_VALUE ? -1 : retVal);
        return cache.get(contentStr);
    }

    public static int[] copyContentNums(int[] contentNums) {
        int[] nums = new int[contentNums.length];
        for (int i = 0; i < contentNums.length; i++) {
            nums[i] = contentNums[i];
        }
        return nums;
    }

    public static void main(String[] args) {
        int minPage = getMinPage("babac", new String[]{"ba", "c", "abcd"});
        System.out.println(minPage);
    }
}
